A cyclical buffer is a mechanism which provides access to a group of data elements stored in consecutive memory locations in a memory device.
Cyclical buffers are frequently used in Digital Signal Processing applications, where the data to be processed are stored in consecutive memory locations of a memory device. While processing the data, a processor scans the memory locations in the memory device in order to access the data at the desired memory locations.
FIG. 1 shows schematically such a cyclical buffer which is assumed to contain M consecutive memory locations starting at a memory location START and terminating at a memory location END such that END=START+M-1.
The cyclical buffer mechanism allows for the same operation to be performed on the elements in a repeated, cyclical manner. The elements are processed, one at a time, starting with the element in memory location START, proceeding until the element in memory location END is reached and then returning to the element in memory location START and then repeating the cycle as required.
The processing mechanism may be stepped whereby the cyclical buffer addressing mechanism is incremented or decremented by an amount equal to STEP after each access so that the elements are processed starting with the element location START, proceeding to START+STEP, and so on as far as END and then repeating the cycle in "STEP" increments as required.
It can easily be shown that the cyclical buffer mechanism is represented by the following algorithm: EQU ELEMENT.sub.-- ADDRESS:=START EQU REPEAT FOR ERROR: EQU ELEMENT.sub.-- ADDRESS:=(ELEMENT.sub.-- ADDRESS+STEP) MODULU (M) and repeat;
wherein: (A) MODULU (n) is defined as: A-[A/B]*B where [A/B] is the integer part of A/B.
Such a mechanism permits successive addresses within the cyclical buffer to be addressed starting at any location and allowing for any value of STEP so that all addressable locations in the cyclical buffer are utilized and ensuring that when the end of the cyclical buffer is reached, the mechanism automatically cycles to the correct address location.
In practice, however, it is found that a high processing price is paid for implementing MODULU function which renders a complete hardware implementation both complex and expensive. Generally, hardware mechanisms allowing for zero penalty scanning of the data elements are used in high performance applications. Usually, an initialization command activates the cyclic buffer process and determines the values of START, M and STEP. Following the execution of the initialization command, the processor starts performing the "operation" on the buffer elements. The hardware mechanism manipulates the data elements. The address manipulation is performed in parallel to the operation execution so that there is no performance penalty in terms of the execution time thereof. However, as stated above, a high penalty is paid in terms of complexity and cost.
It is therefore known in very low cost applications to implement the cyclical buffer using software only. In this case, there is no dedicated hardware for cyclical buffering. A software program accesses the appropriate memory locations, performs the operation on the data elements, calculates the memory address of the next data element, accesses the next element and performs the operation thereon. This cycle is repeated indefinitely.
Such an approach requires additional memory in order to store the software code therein and greatly increases the processing time involved in address calculation and iteration control.
Finally, in mid-range applications a dedicated mechanism allows for zero penalty scanning and provides almost the same fast processing as a dedicated hardware mechanism whilst being constrained to very specific buffer parameters. For example, in one particular implementation, M is an integer power of 2 and START is an integer multiple of M. Such an approach is used in the ZR34325 32-Bit Floating Point Vector Signal Processor manufactured by Zoran and described on pages 37 and 38 of the Manufacturer's Data Specification. Such an approach limits the length of the buffer to 2.sup.n.
Whilst such an approach considerably simplifies the hardware complexity, the restrictions increase the execution time and the required memory space.